#include <stdio.h>
#include <stdlib.h>

//定义最大顶点数，本常量在定义MGraph结构体的顶点和边时，都必须被用到
#define MaxVertexNum 100
typedef enum{FALSE,TRUE} Boolean;

//用邻接矩阵表示的图的类型
typedef struct {
    char Vertices[MaxVertexNum];          //顶点信息的数组
    int Edge[MaxVertexNum][MaxVertexNum]; //边信息的数组
    int ver_num, edge_num;                            //总顶点数，边数
} MGraph;
//广度优先遍历需要的循环队列
typedef struct {
    int data[MaxVertexNum];
    int front, rear;
} Queue;
/****************************************/
//队列的相关操作
//初始化
void InitQueue(Queue *Q) {
    Q->front = Q->rear = 0;
}

//入队
void EnQueue(Queue *Q, int e) {
    if ((Q->rear + 1) % MaxVertexNum == Q->front)
        return;

    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MaxVertexNum;
}

//判空
Boolean QueueEmpty(Queue *Q) {
    if (Q->front == Q->rear)
        return TRUE;
    else
        return FALSE;
}

//出队
void DeQueue(Queue *Q, int *e) {
    if (Q->front == Q->rear)
        return;

    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxVertexNum;
}

// ====查找图G的顶点的编号====
// 编号为构建图G时每个顶点的读入顺序，从0开始。
// 查找到指定顶点名字时，返回对应编号；找不到时，返回-1 。
int locate_vertex(MGraph * G, char vertex_name) {
    int i;
    for(i=0;i<G->ver_num;++i)
        if(vertex_name==G->Vertices[i])
            return i;
    return -1;
}

//=========建立邻接矩阵=======
// 参数 G_pp 是尚未被初始化的 (指向 (指向 MGraph 的指针) 的指针)
// 参数 graph_data_filename 是存储如下格式的图数据的文件名（字符串）：
/*
 * 顶点数 边数
 * 顶点名字序列（用a b c d e 等字符命名）
 * a b // 边1
 * a c // 边2
 * d e // 边3
 */
void create_graph(MGraph ** G_pp, char * graph_data_filename)
{

  FILE * fp;
  size_t len = 0;
  ssize_t read;

  int num_nodes, num_edges;

  fp = fopen(graph_data_filename, "r");
  if (fp == NULL)
    exit(EXIT_FAILURE);

  fscanf(fp, "%d %d\n", &num_nodes, &num_edges);

  // 实现开始：可以自行定义变量，但是不要删掉或者更改对fopen和fclose的调用
    int i,j,k,w,a,t;
    (*G_pp)=(MGraph*)malloc(sizeof(MGraph));

    (*G_pp)->ver_num  = num_nodes;
    (*G_pp)->edge_num = num_edges;
  // 如上，用fscanf从fp里读取字符

    for(i=0; i<(*G_pp)->ver_num; i++)
    {
        fscanf(fp, " %c\n", &((*G_pp)->Vertices[i]));
        printf("%c\n",(*G_pp)->Vertices[i]);


    }
    //初始化邻接矩阵
    for (j = 0; j < num_nodes; j++) {
        for (t = 0; t < num_nodes; t++) {
            (*G_pp)->Edge[j][t]=0;
        }
    }
    char v1,v2;
    for (int k = 0; k < num_edges; k++) {
        v1 = fgetc(fp);
        printf("%c",v1);
        fgetc(fp);
        v2 = fgetc(fp);
        fgetc(fp);
        printf("%c\n",v2);
        for (j = 0; j < num_nodes; j++) {
            for (t = 0; t < num_nodes; t++) {
                if ((*G_pp)->Vertices[t]==v2&&(*G_pp)->Vertices[j]==v1){
                    (*G_pp)->Edge[j][t]=1;
                    (*G_pp)->Edge[t][j]=1;
                }
            }
        }
    }
    for(i=0; i<(*G_pp)->ver_num; i++)
    {
        for(t=0; t<(*G_pp)->ver_num; t++){
            fscanf(fp, " %d\n", &a);

            (*G_pp)->Edge[j][t]=a;

        }


    }
//    for(j=0; i<(*G_pp)->ver_num; j++)
//    {

////        printf("进来没啊\n");
//        printf("进来没啊\n");
//
//    }

    //输出邻接矩阵




  // 实现结束
    printf("邻接矩阵如下：\n");
    for (j = 0; j < num_nodes; j++) {
        for (t = 0; t < num_nodes; t++) {
            printf("%d\t",(*G_pp)->Edge[j][t]);
        }
        printf("\n");
    }

  fclose(fp);
}

//========dfs：深度优先遍历的递归算法======
// 参数 G：指向MGraph的指针
// 参数 i: 从i个顶点开始深度优先遍历。i是顶点在原始数据中 顶点名字序列 里从0开始的位置；比如顶点 b 在 顶点序列 a b c d e f中的位置是 1。
// 参数 visited_order: 当前顶点被访问的全局顺序
// 参数 result_sequence: 用于记录在 当全局访问顺序为 visited_order 时，被访问的结点名字（字符）
void dfs(MGraph *G, int i, Boolean visited[], char * result_sequence, int * visited_order)
{
    int w;
    visited[i] = TRUE; //标记访问第v个顶点
    result_sequence[* visited_order] = G->Vertices[i];
    (* visited_order) ++;
    for(w = 0; w< G->ver_num; w++){
        //依次检查邻接矩阵v所在的行
        if((G->Edge[i][w]!=0)&& (!visited[w])){
            //w是v的邻接点，如果

            dfs(G, w,visited,result_sequence,visited_order);


        }
        if( visited[w]){


        }



    }



}

//===========bfs：广度优先遍历=======
// 参数 G：指向MGraph的指针
// 参数 k: 从k个顶点开始深度优先遍历。k是顶点在原始数据中 顶点名字序列 里从0开始的位置；比如顶点 b 在 顶点序列 a b c d e f中的位置是 1。
// 参数 visited_sequence: 用于记录在广度优先遍历时，依次被访问的顶点的名字
void bfs(MGraph *G, int k, Boolean visited[], char * visited_sequence)
{

    int i, j, count = 0;
    Queue Q;

    for (i = 0; i < G->ver_num; ++i) {
        visited[i] = 0;
    }
    InitQueue(&Q);
    visited[k] = 1;
    visited_sequence[count++] = G->Vertices[k];
    EnQueue(&Q, k);
    while (!QueueEmpty(&Q)) {
        DeQueue(&Q, &i);
        for (j = 0; j < G->ver_num; ++j) {
            if (!visited[j] && G->Edge[i][j] != 0) {
                visited[j] = 1;
                visited_sequence[count++] = G->Vertices[j];
                EnQueue(&Q, j);
            }
        }
    }
}

//==========main=====
void main()
{

  int i;
  MGraph *G;
  Boolean visited[MaxVertexNum];

  for(i=0; i<MaxVertexNum; i++) {
    visited[i] = FALSE;
  }

  create_graph(&G, "graph_data.txt"); //建立邻接矩阵
    printf("ok\n");


  char dfs_sequence[MaxVertexNum] = {'\0'};
  int visited_order = 0;
  dfs(G, 0, visited, dfs_sequence, &visited_order); //深度优先遍历。 应该输出：abdhecfg
  printf("Print Graph DFS: ");
  for(i = 0;i<8;i++){

      printf("%c    ", dfs_sequence[i]);

  }

    printf("\n");
  for(i=0; i<MaxVertexNum; i++) {
    visited[i] = FALSE;
  }
  char bfs_sequence[MaxVertexNum] = {'\0'};
  bfs(G, 0, visited, bfs_sequence); //以序号为3的顶点开始广度优先遍历。应该输出：abcdefgh
  printf("Print Graph BFS: ");
  printf("%s\n", bfs_sequence);
  
  char bfs_sequence2[MaxVertexNum] = {'\0'};
  bfs(G, 3, visited, bfs_sequence2); //以序号为3的顶点开始广度优先遍历。应该输出：dbhaecfg
  printf("Print Graph BFS: ");
  printf("%s\n", bfs_sequence2);
}
